package lanQiaoBei.violent_recursion;

/*
 * 给定两个长度都为N的数组wights和values,weights[i]和values[i]分别表示水果的重量和水果的价值，给定一个袋子bag
 * 它只能放定指定重量的水果，求bag能装的最大水果价值
 * */
public class BuyFruit {
    public static void main(String[] args) {
        System.out.println(realize(new int[]{1, 2, 3,2}, new int[]{1, 2, 3,4}, 5));
    }

    public static int realize(int[] weights, int[] values, int bag) {
        return f(weights, values, bag, 0, 0);
    }

    private static int f(int[] weights, int[] values, int bag, int weight, int i) {
        if(weight>bag){
            return -weights[i-1];
        }
        if (i == weights.length) {
            return 0;
        }
        return Math.max(values[i]+f(weights, values, bag, weight + weights[i],
                i + 1) ,f(weights, values, bag, weight, i + 1));
    }
}
